Deep learning models have achieved huge success in numerous fields, such as computer vision and natural language processing. However, unlike such fields, it is hard to apply traditional deep learning models on the graph data due to the `node-orderless' property. Normally, we use an adjacent matrix to represent a graph, but an artificial and random node-order will be cast on the graphs, which renders the performance of deep models extremely erratic and not robust. In order to eliminate the unnecessary node-order constraint, in this paper, we propose a novel model named Isomorphic Neural Network (IsoNN), which learns the graph representation by extracting its isomorphic features via the graph matching between input graph and templates. IsoNN has two main components: graph isomorphic feature extraction component and classification component. The graph isomorphic feature extraction component utilizes a set of subgraph templates as the kernel variables to learn the possible subgraph patterns existing in the input graph and then computes the isomorphic features. A set of permutation matrices is used in the component to break the node-order brought by the matrix representation. To further lower down the computational cost and identify the optimal subgraph patterns, IsoNN adopts two min-pooling layers to find the optimal matching. The first min-pooling layer aims at finding the best permutation matrix, whereas the second one is used to determine the best templates for the input graph data. Three fully-connected layers are used as the classification component in IsoNN. Extensive experiments are conducted on real-world datasets, and the experimental results demonstrate both the effectiveness and efficiency of IsoNN.

To use neural networks in safety-critical settings it is paramount to provide assurances on their runtime operation. Recent work on ReLU networks has sought to verify whether inputs belonging to a bounded box can ever yield some undesirable output. Input-splitting procedures, a particular type of verification mechanism, do so by recursively partitioning the input set into smaller sets. The efficiency of these methods is largely determined by the number of splits the box must undergo before the property can be verified. In this work, we propose a new technique based on shadow prices that fully exploits the information of the problem yielding a more efficient generation of splits than the state-of-the-art. Results on the Airborne Collision Avoidance System (ACAS) benchmark verification tasks show a considerable reduction in the partitions generated which substantially reduces computation times. These results open the door to improved verification methods for a wide variety of machine learning applications including vision and control.